﻿//2122. 还原原数组
//Alice 有一个下标从 0 开始的数组 arr ，由 n 个正整数组成。她会选择一个任意的 正整数 k 并按下述方式创建两个下标从 0 开始的新整数数组 lower 和 higher ：
//对每个满足 0 <= i < n 的下标 i ，lower[i] = arr[i] - k
//对每个满足 0 <= i < n 的下标 i ，higher[i] = arr[i] + k
//不幸地是，Alice 丢失了全部三个数组。但是，她记住了在数组 lower 和 higher 中出现的整数，但不知道每个整数属于哪个数组。请你帮助 Alice 还原原数组。
//给你一个由 2n 个整数组成的整数数组 nums ，其中 恰好 n 个整数出现在 lower ，剩下的出现在 higher ，还原并返回 原数组 arr 。如果出现答案不唯一的情况，返回 任一 有效数组。
//注意：生成的测试用例保证存在 至少一个 有效数组 arr 。



class Solution {
public:
    vector<int> recoverArray(vector<int>& nums)
    {
        sort(nums.begin(), nums.end());
        //原数组升序 事实上原数组乱序不影响
        //nums[0]必为arr[0]-k;
        //枚举arr[0]+k;
        int n = nums.size();
        for (int i = 1; i < n; i++)
        {
            if (nums[i] == nums[0] || (nums[i] - nums[0]) % 2 != 0)
            {
                continue;
            }
            int k2 = nums[i] - nums[0];
            if (k2 == 0 || k2 % 2 == 1)    continue;
            int k = k2 / 2;
            vector<int> used(n);
            used[0] = true;
            used[i] = true;
            vector<int> ans;
            ans.push_back(nums[0] + k);
            int left = 0, right = i;
            for (int j = 1; j + j < n; j++)
            {
                //找到最小的未使用的arr[j]-k
                while (used[left])
                    left++;
                //搜索arr[j]+k;
                while (right < n && (used[right] || nums[right] - nums[left] != k * 2))
                    right++;
                //不合法
                if (right == n)    break;
                //合法
                ans.push_back(nums[left] + k);
                used[left] = used[right] = true;
            }

            if (ans.size() == n / 2) return ans;
        }
        return {};
    }
};